// 对链表进行插入排序,这个过程是需要原地进行的。

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val: number) {
        this.val = val;
        this.next = null
    }
}

const insertionSortList = function (head: ListNode | null): ListNode | null {
    let curr: ListNode | null = head;
    let order: ListNode = new ListNode(0); // 有序链表的头节点是一个哨兵节点
    while (curr !== null) {
        let next: ListNode | null = curr.next;
        curr.next = null;
        // 插入一个元素，需要两个位置的节点配合
        let orderPrev: ListNode | null = order;
        let orderNext: ListNode | null = order.next;
        while (orderNext !== null && orderPrev !== null) {
            if (orderNext.val > curr.val) { // 如果找到了当前元素在有序链表中的位置
                orderPrev.next = curr;
                curr.next = orderNext;
                break; // 跳出循环
            }
            orderNext = orderNext.next;
            orderPrev = orderPrev.next;
        }
        if (orderNext === null && orderPrev) orderPrev.next = curr; // 说明当前元素是最大的，直接插到有序链表的最后
        curr = next; // 当前元素下移
    }
    return order.next;
};

let test1 = {
    val: 4,
    next: {
        val: 2,
        next: {
            val: 1,
            next: {
                val: 3,
                next: null
            }
        }
    }
}
insertionSortList(test)

// 这道题可以比较好的复习链表操作与插入排序两个知识点
// 首先我们声明一个新的有序链表，头节点为哨兵节点
// 然后扫描原链表，每扫描一个新节点，断开该节点与原链表的联系，断联系前先存储下一个节点next
// 然后扫描有序链表，先找到待插入的结点位置（前一个结点值比当前的大）
// 这里要注意插入一个元素，需要两个位置的节点配合，分别是插入位置前后的两个节点
// 插入完成后就可以立刻退出该循环了
// 在循环的外部我们再判断有序链表是否已经扫描到最后，因为有可能待插入元素是有序链表中最大的元素
// 如果扫描到最后，说明满足我们的猜想，将当前节点插入有序链表的最后
// 然后根据最早存储的下一个节点next，继续扫描无序链表即可。